import collections


class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        def neighbors(ss):
            # 找到第1个和B不同的字符
            i = 0
            while ss[i] == B[i]:
                i += 1

            # 遍历第1个和B不同的字符的所有可以交换的位置
            tt = list(ss)
            for j in range(i + 1, len(ss)):
                if ss[j] == B[i]:
                    tt[i], tt[j] = tt[j], tt[i]
                    yield "".join(tt)
                    tt[j], tt[i] = tt[i], tt[j]

        # 广度优先搜索
        queue = collections.deque([A])
        cache = {A: 0}
        while queue:
            s = queue.popleft()
            if s == B:
                return cache[s]
            for t in neighbors(s):
                if t not in cache:
                    cache[t] = cache[s] + 1
                    queue.append(t)


if __name__ == "__main__":
    print(Solution().kSimilarity(A="ab", B="ba"))  # 1
    print(Solution().kSimilarity(A="abc", B="bca"))  # 2
    print(Solution().kSimilarity(A="abac", B="baca"))  # 2
    print(Solution().kSimilarity(A="aabc", B="abca"))  # 2

    # 测试用例47/57
    print(Solution().kSimilarity("aabbccddee", "cdacbeebad"))  # 6

    # 测试用例55/57
    print(Solution().kSimilarity("abcdefabcdefabcdef",
                                 "edcfbebceafcfdabad"))  # 10
